COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00009 00003	.skip 1
C00010 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source;
.CB AN INTUITIVE EVALUATION OF THE CATALAN NUMBERS
.turn on "↑"

.ONCE CENTER
JOHN MCCARTHY


	The set ⊗S of non-associative product expressions that
can be formed from a set ⊗A of atoms can be regarded as satisfying
the formal equation

!!a1:	%2S = A + S%8x%2S%1,

i.e. a memeber of ⊗S is either an element of ⊗A or an ordered pair
of elements of ⊗S. 

	Had we the courage of an 18th century mathematician, we would
regard the above as a quadratic equation for ⊗S, solve it by the quadratic
formula, expand the square root by the binomial theorem in powers
of ⊗A, juggle the factorials and binomial coefficients and obtain

	%2S = A + A↑2 + 2A↑3 + 5A↑4 + ... + C%4n-1%2A↑n + ...%1,

where

	%2C%4n%2 = (2n over n)/(n+1)%1

is the %2n%1th Catalan number.
We interpret this as saying that ⊗S is
isomorphic to one copy of the ⊗A plus one copy of the ordered pairs
elements of ⊗A plus two copies of the triplets, etc.

	The result of this 18th century mathematics can be justified if we
imagine ourselves to substitute ({eq a1}) into itself repeatedly,
obtaining at the first step

	%2S = A + (A + S%8x%2S)%8x%2(A + S%8x%2S)%1

and expand by a set-theoretic distributive law to get ⊗S as an infinite
union of Cartesian products.

	We then note that the ordinary quadratic

	%2x = a + x↑2%1

could be expanded by successive substitutions in the same way to

	%2x = a + (a + x↑2)(a + x↑2) = a + a↑2 + 2a x↑2 + x↑4 = ...%1

etc., and would give the same coefficients, since the expansion process
is the same.  But the coefficients of the quadratic can
also be obtained by the quadratic formula and the binomial theorem.
By elementary complex variable, the radius of convergence of the
power series is 1/4.
.skip 1
.begin verbatim
John McCarthy
Artificial Intelligence Laboratory
Computer Science Department
Stanford University
Stanford, California 94305

ARPANET: MCCARTHY@SU-AI
.end

.turn on "{"
%7This version of
CATALA[E78,JMC]
translated for printing (by PUB) at {time} on {date}.%1